package leetcode.problems.P1444切披萨的方案数;

import java.util.Arrays;

public class Ways {
}

// 记忆化搜索 TODO
//class Solution {
//    int MOD = 1000_000_007;
//    int[][] preSum;
//    int m, n;
//    int[][][] memo; // -1 无法切分，0 没有尝试，>0 表示切分方式
//
//    public int ways(String[] pizza, int k) {
//        m = pizza.length;
//        if (m < 1) {
//            return 0;
//        }
//        n = pizza[0].length();
//        calculatePreSum(pizza);
//        memo = new int[m][n][k];
//        return dfs(0, 0, k - 1);
//    }
//
//    // 计算以(leftUpperX, leftUpperY)为左上角、(m-1, n-1)为右下角的pizza切cuts刀的总切法数
//    private int dfs(int leftUpperX, int leftUpperY, int cuts) {
//        // 先查记忆数组
//        if (memo[leftUpperX][leftUpperY][cuts] > 0) {
//            return memo[leftUpperX][leftUpperY][cuts];
//        }
//        if (memo[leftUpperX][leftUpperY][cuts] == -1) {// 已经搜索过，但没有切分结果
//            return 0;
//        }
//        if (cuts == 0) {// 最后一块pizza
//            if (getMatrixAreaSum(leftUpperX, leftUpperY, m - 1, n - 1) > 0) {// 检查切出来的部分有没有苹果
//                memo[leftUpperX][leftUpperY][cuts] = 1;
//                return 1;
//            }
//            memo[leftUpperX][leftUpperY][cuts] = -1;
//            return 0;
//        }
//        int verticalSum = 0, horizontalSum = 0;
//        // 垂直切
//        for (int y = leftUpperY + 1; y < n; y++) {
//            if (getMatrixAreaSum(leftUpperX, leftUpperY, m - 1, y) > 0) {// 切出来的部分有苹果
//                verticalSum += dfs(leftUpperX, y, cuts - 1);
//                verticalSum %= MOD;
//            }
//        }
//
//        // 水平切
//        for (int x = leftUpperX + 1; x < m; x++) {
//            if (getMatrixAreaSum(leftUpperX, leftUpperY, x, n - 1) > 0) {// 切出来的部分有苹果
//                horizontalSum += dfs(x, leftUpperY, cuts - 1);
//                horizontalSum %= MOD;
//            }
//        }
//        return memo[leftUpperX][leftUpperY][cuts] = (verticalSum + horizontalSum) % MOD;
////        return memo[leftUpperX][leftUpperY][cuts];
//    }
//
//    // 计算二维矩阵前缀和，preSum[i][j]表示以(0,0)为左上角、(i,j)为右下角的子矩阵的面积
//    private void calculatePreSum(String[] pizza) {
//        preSum = new int[m][n];
//        for (int i = 0; i < m; i++) {
//            char[] ithRow = pizza[i].toCharArray();
//            for (int j = 0; j < n; j++) {
//                int area1 = 0, area2 = 0, area3 = 0, area4 = ithRow[j] == 'A' ? 1 : 0;
//                if (j > 0) {
//                    area1 = preSum[i][j - 1];
//                }
//                if (i > 0) {
//                    area2 = preSum[i - 1][j];
//                }
//                if (i > 0 && j > 0) {
//                    area3 = preSum[i - 1][j - 1];
//                }
//                preSum[i][j] = area1 + area2 - area3 + area4;
//            }
//        }
//    }
//
//    // 根据前缀和数组preSum，计算以(leftUpperX,leftUpperY)为左上角、(rightLowerX,rightLowerY)为右下角的子矩阵的面积
//    private int getMatrixAreaSum(int leftUpperX, int leftUpperY, int rightLowerX, int rightLowerY) {
//        int area1 = preSum[rightLowerX][rightLowerY], area2 = 0, area3 = 0, area4 = 0;
//        if (leftUpperX > 0) {
//            area2 = preSum[leftUpperX - 1][rightLowerY];
//        }
//        if (leftUpperY > 0) {
//            area3 = preSum[leftUpperX][leftUpperY - 1];
//        }
//        if (leftUpperX > 0 && leftUpperY > 0) {
//            area4 = preSum[leftUpperX - 1][leftUpperY - 1];
//        }
//        return area1 - area2 - area3 + area4;
//    }
//}

class Solution {
    int MOD = 1000_000_007;
    MatrixSum preSum;
    int m, n;
    int[][][] memo; // -1 无法切分，0 没有尝试，>0 表示切分方式

    public int ways(String[] pizza, int k) {
        m = pizza.length;
        if (m < 1) {
            return 0;
        }
        n = pizza[0].length();
        preSum = new MatrixSum(pizza);
        memo = new int[m][n][k];// memo(i,j,k)=-1未访问，>=0表示以(i,j)为左上角、(m-1,n-1)为右下角的披萨切k刀的切法数
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                Arrays.fill(memo[i][j], -1);
            }
        }
        return dfs(0, 0, k - 1);
    }

    // 计算以(leftUpperX, leftUpperY)为左上角、(m-1, n-1)为右下角的pizza切cuts刀的总切法数
    private int dfs(int leftUpperX, int leftUpperY, int cuts) {
        if (memo[leftUpperX][leftUpperY][cuts] != -1) {// 已经搜索过
            return memo[leftUpperX][leftUpperY][cuts];
        }
        if (cuts == 0) {// 最后一块pizza
            return preSum.query(leftUpperX, leftUpperY, m - 1, n - 1) > 0 ? 1 : 0;
        }
        int sum = 0;
        for (int y = leftUpperY + 1; y < n; y++) {// 垂直切
            if (preSum.query(leftUpperX, leftUpperY, m - 1, y - 1) > 0) {// 切出来的部分有苹果
                sum += dfs(leftUpperX, y, cuts - 1);
                sum %= MOD;
            }
        }
        for (int x = leftUpperX + 1; x < m; x++) {// 水平切
            if (preSum.query(leftUpperX, leftUpperY, x - 1, n - 1) > 0) {// 切出来的部分有苹果
                sum += dfs(x, leftUpperY, cuts - 1);
                sum %= MOD;
            }
        }
        return memo[leftUpperX][leftUpperY][cuts] = sum;
    }

    private static class MatrixSum {
        int[][] sum;
        int m, n;

        MatrixSum(String[] matrix) {
            m = matrix.length;
            if (m < 1) {
                return;
            }
            n = matrix[0].length();
            sum = new int[m][n];
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    int area1 = 0, area2 = 0, area3 = 0, area4 = matrix[i].charAt(j) == 'A' ? 1 : 0;
                    if (j > 0) {
                        area1 = sum[i][j - 1];
                    }
                    if (i > 0) {
                        area2 = sum[i - 1][j];
                    }
                    if (i > 0 && j > 0) {
                        area3 = sum[i - 1][j - 1];
                    }
                    sum[i][j] = area1 + area2 - area3 + area4;
                }
            }
        }

        // 计算以(r1,c1)为左上角、(r2,c2)为右下角的子矩阵的面积(包含坐标)
        public int query(int r1, int c1, int r2, int c2) {
            int area1 = sum[r2][c2], area2 = 0, area3 = 0, area4 = 0;
            if (r1 > 0) {
                area2 = sum[r1 - 1][c2];
            }
            if (c1 > 0) {
                area3 = sum[r2][c1 - 1];
            }
            if (r1 > 0 && c1 > 0) {
                area4 = sum[r1 - 1][c1 - 1];
            }
            return area1 - area2 - area3 + area4;
        }
    }
}
